public class MyLinkList {

    static class ListNode {
        public int value;
        public ListNode next;

        //构造器
        public ListNode(int value) {
            this.value = value;
        }

    }

    public ListNode head;

    //此处的 create 并不是真正创建链表的方式 在此处 这样创建 只是为了 方便初学者理解
    public void create(){
        //listNode1、listNode2、listNode3、listNode4、listNode5 都是局部变量
        //等链表创建结束之后 局部变量 会被回收
        //此时只剩 head 存在 因为 head是 全局变量
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(23);
        ListNode listNode3 = new ListNode(34);
        ListNode listNode4 = new ListNode(45);
        ListNode listNode5 = new ListNode(56);

        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        this.head = listNode1;
    }

    public void display(){
        //此处用head节点不太合适 因为头节点 相当于链表的头部标记
        //而此处的head 会随着while 循环的进行 一直到最后 最终变为null

//        while(head != null){
//            System.out.print(head.value + " ");
//            head = head.next;
//        }

        //所以我们需要找一个“替身”
        // :)
        ListNode myStanding = head;
        while (myStanding != null){
            System.out.print(myStanding.value + " ");
            myStanding = myStanding.next;
        }

        //上面standing 是 在开玩笑 :)
        //一般我们用 cur 命名
//        ListNode cur = head;
//        while (cur != null){
//            System.out.println(cur.value + " ");
//            cur = cur.next;
//        }

        System.out.println();
    }

    //得到单链表的长度
    public int size() {
        //方法中定义的变量是 局部变量
        //作用域范围只在方法中
        //等方法调用结束之后 局部变量就消失
        //这也是 为什么 display方法中会有 cur 变量
        //此处也有 cur 变量

        ListNode cur = head;
        int count = 0;
        if(cur != null){
            while(cur != null){
                count++;
                cur = cur.next;
            }
            return count;
        }else {
            return -1;
        }

    }

    //头插法
    public void addFirst(int data) {
        if(head != null){
            ListNode newNode = new ListNode(data);
            newNode.next = head;
            head = newNode;
        } else {
            ListNode newNode = new ListNode(data);
            head = newNode;
        }

        //其实不加else 只有if语句中的 代码 也可以实现 各个情况下的头插

    //总结： 插入节点的时候 首先先绑定 后边的节点
    }

    //尾插法
    public void addLast(int data) {
        ListNode newNode = new ListNode(data);
        ListNode cur = head;

        if(head != null){
            //既然要尾插  ， 我们 要先找到最后一个节点
            while(cur.next != null){
                cur = cur.next;
            }

            //经过while循环之后，此处的 cur 就是 最后一个节点 的位置
            cur.next = newNode;
        } else {
            head = newNode;
            //此处千万不要忘加return，因为我们尾插的逻辑在此处已经可以算是结束了，
            // 假设后面还有很长的代码 ，没有return的话 会继续执行后面的代码 直到所有代码执行完毕
            return;
        }


    }

    //任意位置插入,第一个数据节点为0号下标
    //此方法是在 指定位置后插入
//    public void addIndex(int index, int data) {
//        ListNode newNode = new ListNode(data);
//        ListNode cur = head;

        //判断index的位置是否合法
//        try{
//            checkIndex(index);
//        } catch (IndexNotLegalException e){
//            e.printStackTrace();
//        }
//
//        if (index == 0){
//            addFirst(data);
//            return;
//        }
//
//        if (index == size()){
//            addLast(data);
//            return;
//        }
//
         //
//        if(head != null){
//           for(int i = 0; i < index - 1; i++){
////            cur = cur.next;
////        }
//
//            while(index - 1 > 0){
//                index--;
//                cur = cur.next;
//            }
//
//            newNode.next = cur.next;
//            cur.next = newNode;
//
//            return;
//        }
//
//    }


    //任意位置插入,第一个数据节点为0号下标
    //此方法是在 指定位置前插入
    public void addIndex2(int index, int data) {
        ListNode newNode = new ListNode(data);
        ListNode cur = head;
        try {
            checkIndex(index);
        } catch (IndexNotLegalException e){
            e.printStackTrace();
        }

        if (index == 0){
            addFirst(data);
            //return 一定不要忘记加
            return;
        }

        if (index == size()){
            addLast(data);
            //return 一定不要忘记加
            return;
        }

        if(head != null){

//        for(int i = 0; i < index; i++){
//            cur = cur.next;
//        }

            while(index - 1 > 0){
                index--;
                cur = cur.next;
            }

            newNode.next = cur.next;
            cur.next = newNode;

            //return 一定不要忘记加
            return;
        }

    }

    private void checkIndex(int index) throws IndexNotLegalException{
        if(index < 0 || index > size()){
            throw new IndexNotLegalException("index位置不合法");
        }
    }

    private ListNode findIndexsubOne(int index){
        ListNode cur = head;
//        if(head != null){
//            while(index > 0){
//                index--;
//                cur = cur.next;
//            }
//        }

        //也可以使用计数器
        int count = 0;
        while (count != index - 1){
            cur = cur.next;
            count++;
        }
        return cur;

    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
       ListNode cur = head;
//        while(cur != null && cur.value != key) {
//            cur = cur.next;
//        }
//
//        if(cur == null){
//            return false;
//        }
//
//        return true;

        while(cur != null){
            if(cur.value == key){
                return true;
            }
            cur = cur.next;
        }
        return false;

    }

    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        if(head == null){
            return;
        }

        if(head.value == key){
            head = head.next;
            return;
        }

        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.value == key){
                cur.next = cur.next.next;
                return;
            }
            cur = cur.next;
        }


    }

    //删除所有值为key的节点
    public void removeAllKey(int key) {
        if(head == null){
            return;
        }

        ListNode prev = head;
        ListNode cur = head.next;

        while(cur != null){
            if(cur.value == key){
                prev.next = cur.next;
//                cur = cur.next;
            } else{
                prev = cur;
//                cur = cur.next;
            }

            cur = cur.next;
        }

        if(head.value == key){
            head = head.next;
        }

    }



}
